package dk;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class StringDistances {
	util u = new util();
	
	
	
	// Taken right from web. Not the fastest. Used as a benchmark
	
//	http://www.funzytech.com/?p=93
	public int levenBasicWeb (String s, String t) {
		if (s == null || t == null) {
		throw new IllegalArgumentException("Strings must not be null");
		}

		int n = s.length();
		int m = t.length();

		if (n == 0) {
		return m;
		}

		else if (m == 0) {
		return n;
		}

		int p[] = new int[n+1];
		int d[] = new int[n+1];
		int _d[];
		int i;
		int j;

		char t_j;

		int cost;

		for (i = 0; i<=n; i++) {
		p[i] = i;
		}

		for (j = 1; j<=m; j++) {
		t_j = t.charAt(j-1);
		d[0] = j;

		for (i=1; i<=n; i++) {
		cost = s.charAt(i-1)==t_j ? 0 : 1;

		d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]+cost);
		}
		_d = p;
		p = d;
		d = _d;
		}

		//Determine percentage difference
		double levNum = (double)p[n];
		double percent = (levNum/Math.max(s.length(),t.length()))*100;
		int percentDiff = (int)percent;

		return percentDiff;
		}
	
	
	// Determine if two files have the same contents
			// Should probably think about ignoring the first line of the file???
			//	-- It depends what information that first line has?
	/*
			public boolean isFilesSame(String inputFile1, String inputFile2) throws IOException{
				boolean retVal = true;
				
				 	BufferedReader bfr2 = new BufferedReader(new InputStreamReader(System.in));
				    String s1 = "";
				    String s2 = "", s3 = "", s4 = "";
				    String y = "", z = "";
				    
				    File file1 = new File(inputFile1);
				    File file2= new File(inputFile2);
				    
				    BufferedReader bfr = new BufferedReader(new FileReader(file1));
				    BufferedReader bfr1 = new BufferedReader(new FileReader(file2));

				    while ((z = bfr1.readLine()) != null)
				        s3 += z;

				    while ((y = bfr.readLine()) != null)
				        s1 += y;

				 //   System.out.println();
//				    System.out.println(s3);

				    if (s3.equals(s1)) {
				   //     System.out.println("Content of both files are same");
				    	retVal=true;
				    } else {

				      //  System.out.println("Content of both files are not same");
				    	retVal=false;
				    }
				    
			return retVal;
			}

	*/
	
	
	/*
	// determine if two files have the same contents (except for the first lines)
	public boolean isFilesSame(String inputFile1, String inputFile2) throws IOException{
		String fileContents1="";
		String fileContents2="";
		File file1 = new File(inputFile1);
		File file2 = new File(inputFile2);
		fileContents1=u.getCompleteFileContents(file1).replace(" ", "");
		fileContents2=u.getCompleteFileContents(file2).replace(" ", "");
		
		if(fileContents1.equals(fileContents2)){
			return true;
		}else{
			return false;
		}
	}
	*/
	
	public int getMaxNumberMatchingLineSequenceInFiles(String inputFile1, String inputFile2){
		File file1 = new File(inputFile1);
		File file2 = new File(inputFile2);
	//	CA.Helper h = new CA.Helper();
		util u = new util();
		int maxLongestSequenceCounter=0;
		int currentLongestSequenceCounter=0;
		
		for (int i = 2; i <= u.getMinLineCount(file1, file2); i++) {
			if((u.getLineInformation(file1,i).trim().equals(u.getLineInformation(file2,i).trim()))){
				currentLongestSequenceCounter = currentLongestSequenceCounter+1;
				
				if (currentLongestSequenceCounter > maxLongestSequenceCounter){
					maxLongestSequenceCounter = currentLongestSequenceCounter;
				}
			}else{
				//System.out.println("Reset Counter at :" +currentLongestSequenceCounter );
				currentLongestSequenceCounter=0; // reset the counter
			}
		}
	
		return maxLongestSequenceCounter;
	}
	
	
	public int getStringDifference(String a, String b)
	{
	    // Minimize the amount of storage needed:
	    if (a.length() > b.length())
	    {
	    	// Swap:
	    	String x = a;
	    	a = b;
	    	b = x;
	    }
	    
	    // Store only two rows of the matrix, instead of a big one
	    int[] mat1 = new int[a.length() + 1];
	    int[] mat2 = new int[a.length() + 1];

	    int i;
	    int j;

	    for (i = 1; i <= a.length(); i++)
	    	mat1[i] = i;

	    mat2[0] = 1;

	    for (j = 1; j <= b.length(); j++)
	    {
	    	for (i = 1; i <= a.length(); i++)
	    	{
	    		int c = (a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1);

	    		mat2[i] =
	    			Math.min(mat1[i - 1] + c,
	    			Math.min(mat1[i] + 1, mat2[i - 1] + 1));
	    	}

	    	// Swap:
	    	int[] x = mat1;
	    	mat1 = mat2;
	    	mat2 = x;

	    	mat2[0] = mat1[0] + 1;
	    }

	    // It's row #1 because we swap rows at the end of each outer loop,
	    // as we are to return the last number on the lowest row
	    return mat1[a.length()];
	}
	
	/*
	// get the differences divided by the number of characters
	public double getStringDiffByCharCount(String a, String b){
		double retVal=0;
		File file1 = new File(a);
		File file2 = new File(b);
		double file1Count = u.getCompleteFileContents(file1).length();
		double file2Count = u.getCompleteFileContents(file2).length();

		
	//	System.out.println(getStringDifference(a, b));
	//	System.out.println(file1Count);
	//	System.out.println(file2Count);
		
		return getStringDifference(a, b)/(file1Count + file2Count);
	}
	*/
	
	// get the differences divided by the number of characters
	// get the differences divided by the number of characters
	public double getStringDiffByLineCount(String a, String b){
		double retVal=0;
		File file1 = new File(a);
		File file2 = new File(b);
		
		double file1Count= u.getFileLineCount(file1);
		double file2Count= u.getFileLineCount(file2);
	//	getStringDifference(a, b);
		
	//	System.out.println(getStringDifference(a, b));
	//	System.out.println(u.getFileLineCount(file1));
	//	System.out.println(u.getFileLineCount(file1));
		
		
		return getStringDifference(a, b)/(file1Count + file2Count);
	}
	
	
	public int LevenDistance(String s1, String s2) {
	    s1 = s1.toLowerCase();
	    s2 = s2.toLowerCase();
	 
	    int[] costs = new int[s2.length() + 1];
	    for (int i = 0; i <= s1.length(); i++) {
	      int lastValue = i;
	      for (int j = 0; j <= s2.length(); j++) {
	        if (i == 0)
	          costs[j] = j;
	        else {
	          if (j > 0) {
	            int newValue = costs[j - 1];
	            if (s1.charAt(i - 1) != s2.charAt(j - 1))
	              newValue = Math.min(Math.min(newValue, lastValue), costs[j]) + 1;
	            costs[j - 1] = lastValue;
	            lastValue = newValue;
	          }
	        }
	      }
	      if (i > 0)
	        costs[s2.length()] = lastValue;
	    }
	    return costs[s2.length()];
	  }

	
	public double leven1a (String s, String t) {
		if (s == null || t == null) {
		throw new IllegalArgumentException("Strings must not be null");
		}

		int n = s.length();
		int m = t.length();

		if (n == 0) {
		return m;
		}

		else if (m == 0) {
		return n;
		}

		int p[] = new int[n+1];
		int d[] = new int[n+1];
		int _d[];
		int i;
		int j;

		char t_j;

		int cost;

		for (i = 0; i<=n; i++) {
		p[i] = i;
		}

		for (j = 1; j<=m; j++) {
		t_j = t.charAt(j-1);
		d[0] = j;

		for (i=1; i<=n; i++) {
		cost = s.charAt(i-1)==t_j ? 0 : 1;

		d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]+cost);
		}
		_d = p;
		p = d;
		d = _d;
		}
		
		
		
		double levNum = (double)p[n];
	//	System.out.println("Leven 1a val:" + levNum);

		//Determine percentage difference
		
		return levNum;
		}
	
	
	 // ?????Is there a need to determine them by length?
	// http://www.funzytech.com/?p=93
	public int LevenDistance2 (String inputS, String inputT) {
		

	
		
		// Skip the first few rows of the comparision.
		//	Might want to refactor this.
		String s = "";
		String t = "";

		for(int x=0; x<inputS.split("\n").length;x++){
			if(x>3){
				s += inputS.split("\n")[x] + "\n";
			}
		}
		
		for(int x2=0; x2<inputT.split("\n").length;x2++){
			if(x2>3){
				t += inputT.split("\n")[x2] + "\n";
			}
		}
		

			
		if (s == null || t == null) {
			throw new IllegalArgumentException("Strings must not be null");
		}

		int n = s.length();
		int m = t.length();

		if (n == 0) {
			return m;
		}

		else if (m == 0) {
			return n;
		}

		int p[] = new int[n+1];
		int d[] = new int[n+1];
		int _d[];
		int i;
		int j;

		char t_j;

		int cost;

		for (i = 0; i<=n; i++) {
			p[i] = i;
		}

		for (j = 1; j<=m; j++) {
		t_j = t.charAt(j-1);
		d[0] = j;

		for (i=1; i<=n; i++) {
		cost = s.charAt(i-1)==t_j ? 0 : 1;

		d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]+cost);
		}
		_d = p;
		p = d;
		d = _d;
		}

		//Determine percentage difference
		double levNum = (double)p[n];
		double percent = (levNum/Math.max(s.length(),t.length()))*100;
		final int percentDiff = (int)percent;

	//	System.out.println("diff:" + percentDiff);
		return percentDiff;
	}
	
	
	




	
	
	// http://stackoverflow.com/questions/13564464/problems-with-levenshtein-algorithm-in-java
//	public int LevenDistance3( char[] s1, char[] s2 ) {
	public double LevenDistance3 (String inputS, String inputT) {
		
		String s = "";
		String t = "";
// s1 = inputs
// s2 = inputT
		
		
		char[] s1 = inputS.toCharArray();
		char[] s2 = inputT.toCharArray();
		
	    // memoize only previous line of distance matrix     
	    int[] prev = new int[ s2.length + 1 ];

	    for( int j = 0; j < s2.length + 1; j++ ) {
	        prev[ j ] = j;
	    }

	    for( int i = 1; i < s1.length + 1; i++ ) {

	        // calculate current line of distance matrix     
	        int[] curr = new int[ s2.length + 1 ];
	        curr[0] = i;

	        for( int j = 1; j < s2.length + 1; j++ ) {
	            int d1 = prev[ j ] + 1;
	            int d2 = curr[ j - 1 ] + 1;
	            int d3 = prev[ j - 1 ];
	            if ( s1[ i - 1 ] != s2[ j - 1 ] ) {
	                d3 += 1;
	            }
	            curr[ j ] = Math.min( Math.min( d1, d2 ), d3 );
	        }

	        // define current line of distance matrix as previous     
	        prev = curr;
	    }

	    return prev[ s2.length ];
	    
		//Determine percentage difference
		//double levNum = (double)p[n];
	    /*
	    double levNum = (double)prev[ s2.length ];
		double percent = (levNum/Math.max(s.length(),t.length()))*100;
		final int percentDiff = (int)percent;

	//	System.out.println("diff:" + percentDiff);
		return percentDiff;
	    */
	}
	
	
	public int getLevenValue(String val1, String val2){
		return (int) Math.round(LevenDistance3(val1, val2));
	//	return (int) Math.round(LevenDistance2(val1, val2));
	
	}
	
	
	
	public int getLevenPercentVal(String val1, String val2){
	//	double levNum = leven1a(val1, val2);
		double levNum = LevenDistance3(val1, val2);
		double percent = (levNum/Math.max(val1.length(),val2.length()))*100;
		int percentDiff = (int)percent;

		return percentDiff;
		
		
	}
	
		
	
	
}


